#lang scheme

; TODO: btree (256-entry pages, insert into middel, append to the end)
; TODO: radix tree
(require "my.ss")

(provide wt-length
         wt wt/sort iter->wt list->wt
         wt-first wt-last
         wt-height wt-mheight
         wt-for-each wt-fold wt-fold-right
         wt->list wt->vector
         wt-get
         wt-update wt-replace wt-insert wt-remove
         
         list->wt/sort
         wt-concat
         wt-split< wt-split>
         wt-union
         wt-intersection
         wt-ref wt-ins
         wt-ref-it
         wti-n
         wt-first-it wt-last-it
         wti=?
         wti-value
         wti-next wti-prev
         wt->iter wt->iter/backward
         
         wt-edge+
         wt-edge-
         wt-edgei+
         wt->iter+
         )
;;  Test code, using maps from digit strings to the numbers they represent.

(define (wt-length node)
  (match node
    ['()         0]
    [#(_ _ _ w)  w]
    [v           1])) ; N1=identity


; eager
;(define (N1 v) (vector v '() '() 1))
;(define (N1 v) v)
(define (N v l r [w (+ 1 (wt-length l) (wt-length r))]) (vector v l r w))
; lazy
;(define (N k v l r [w 0]) (vector k v l r w))


(define wt-ratio 4)

(define (balance v l r)
  (let ([lw (wt-length l)]
        [rw (wt-length r)])
    (cond [(< (+ lw rw) 3)        (N v l r)]
          ;; right is too big
          [(> rw (* wt-ratio lw)) (match-let ([#(rv rl rr _) r])
                                    (if (<= (wt-length rl) (wt-length rr))
                                        (N rv (N v l rl) rr)
                                        (match-let ([#(rlv rll rlr _) rl])
                                          (N rlv (N v l rll) (N rv rlr rr)))))]
          ;; left is too big
          [(> lw (* wt-ratio rw)) (match-let ([#(lv ll lr _) l])
                                    (if (<= (wt-length lr) (wt-length ll))
                                        (N lv ll (N v lr r))
                                        (match-let ([#(lrv lrl lrr _) lr])
                                          (N lrv (N lv ll lrl) (N v lrr r)))))]
          [else                    (N v l r)])))


(define (iter->wt it)
  (iter->tree it '() identity N))

(define (list->wt lst)
  (iter->wt (list->iter lst)))

(define (wt . lst)
  (list->wt lst))

(define (wt/sort cmp . lst)
  (list->wt/sort cmp lst))

(define (_wt-first-node node)
  (match node
    ['()           (error 'min)]
    [#(_ '() _ _)  node]
    [#(_   l _ _)  (_wt-first-node l)]))

(define (_wt-last-node node)
  (match node
    ['()           (error 'max)]
    [#(_ _ '() _)  node]
    [#(_ _   r _)  (_wt-last-node r)]))

(define (wt-first node)
  (match node
    ['()           (error 'min)]
    [#(v '() _ _)  v]
    [#(_   l _ _)  (wt-first l)]
    [v             v]))

(define (wt-last node)
  (match node
    ['()           (error 'max)]
    [#(v _ '() _)  v]
    [#(_ _   r _)  (wt-last r)]
    [v             v]))

; TODO: the same using less?
;(define (wt-get-node cmp x node)
;  (let loop ([node node])
;    (match node
;      ['()         #f]
;      [#(v l r _)  (if3 (cmp x v)
;                        (loop l)
;                        node
;                        (loop r))])))

(define (wt-get cmp node x)
  (let loop ([node node])
    (match node
      ['()         #f]
      [#(v l r _)  (if3 (cmp x v)
                        (loop l)
                        v
                        (loop r))]
      [v           (if3 (cmp x v) #f v #f)])))

;; (a -> a -> integer) -> wt -> a -> wt
(define (wt-remove cmp node x)
  (let loop ([node node])
    (match node
      ['()        '()]
      [#(v l r _) (if3 (cmp x v)
                       (balance v (loop l) r)
                       (_wt-concat2 l r)
                       (balance v l (loop r)))]
      ; N1=identity
      [v          (if3 (cmp x v)
                       v
                       '() ;(_wt-concat2 '() '())
                       v)]
      )))

(define (wt-height node)
  (match node
    ['() 0]
    [#(_ l r _)  (+ 1 (max (wt-height l)
                           (wt-height r)))]
    [_ 1]))

; minimal height
(define (wt-mheight node)
  (match node
    ['() 0]
    [#(_ l r _)  (+ 1 (min (wt-mheight l)
                           (wt-mheight r)))]
    [_ 1]))

(define (wt-for-each proc node)
  (let loop ([node node])
    (match node
      ['()        (void)]
      [#(v l r _) (loop l)
                  (proc v)
                  (loop r)]
      [v          (proc v)]))
  (void))

(define (wt-fold f acc node)
  (match node
    ['()         acc]
    [#(v l r _)  (wt-fold f (f v (wt-fold f acc l)) r)]
    [v           (f v acc)])) ; N1=identity

(define (wt-fold-right f acc node)
  (match node
    ['()         acc]
    [#(v l r _)  (wt-fold-right f (f v (wt-fold-right f acc r)) l)]
    [v           (f v acc)])) ; N1=identity

;; wt -> list
(define (wt->list node)
  (wt-fold-right cons '() node))

;; wt -> vector
(define (wt->vector node)
  (let ([it (wt->iter node)])
    (build-vector (wt-length node) (lambda(_) (it)))))


; -> (wt oldv status)
(define (wt-update cmp mutator node)
  (let loop ([node node])
    (match node 
      ['()        (values (mutator #f) #f 'inserted)] ; inserting
      [#(v l r _) (if3 (cmp v)
;                       (balance v (loop l) r)
                       (let-values ([(l1 oldv status) (loop l)])
                         (values (case status
                                   [(the-same) node]
                                   [else (balance v l1 r)]) oldv status))
                       (let ([new-v (mutator v)])
                         (if (eq? new-v v) ; nothing realy changed
                             (values node v 'the-same)
                             (values (N new-v l r) v 'replaced)))
                       ;(balance v l (loop r))
                       (let-values ([(r1 oldv status) (loop r)])
                         (values (case status
                                   [(the-same) node]
                                   [else (balance v l r1)]) oldv status)))]
      [v          (if3 (cmp v)
                       (values (N v (mutator #f) '()) #f 'inserted)
                       (let ([new-v (mutator v)])
                         (if (eq? new-v v) ; nothing realy changed
                             (values v v 'the-same)
                             (values new-v v 'replaced)))
                       (values (N v '() (mutator #f)) #f 'inserted))])))

;; (a -> a -> integer) -> wt -> a -> wt
;(define (wt-insert  cmp node x)
;  (values-first (wt-update (lambda(v)(cmp x v)) (lambda(v) (or v x)) node)))
(define (wt-insert cmp node x)
  (let loop ([node node])
    (match node 
      ['()        x] ; inserting
      [#(v l r _) (if3 (cmp x v)
                       (balance v (loop l) r)
                       v ; (N x l r) ; not replacing
                       (balance v l (loop r)))]
      [v          (if3 (cmp x v)
                       (N v x '())
                       v ; x ; not replacing
                       (N v '() x))])))

;; (a -> a -> integer) -> wt -> a -> wt
;(define (wt-replace cmp node x)
;  (values-first (wt-update (lambda(v)(cmp x v)) (const x) node)))
(define (wt-replace cmp node x)
  (let loop ([node node])
    (match node 
      ['()        x] ; inserting
      [#(v l r _) (if3 (cmp x v)
                       (balance v (loop l) r)
                       (N x l r) ; replacing
                       (balance v l (loop r)))]
      [v          (if3 (cmp x v)
                       (N v x '())
                       x ; replacing
                       (N v '() x))])))


(define (list->wt/sort cmp xs)
  (foldl (lambda (x node) (wt-replace cmp node x)) '() xs))

(define (_wt-delmin node)
  (match node
    ['()           (error 'delmin)]
    [#(_ '() r _)  r]
    [#(v   l r _)  (balance v (_wt-delmin l) r)]
    [v             '()] ; N1=identity
    ))


(define (wt-concat a b)
  (cond ((empty? a)  b)
        ((empty? b)  a)
        (else  (balance (wt-first b) a (_wt-delmin b))))) ; TODO?: N

(define (_wt-concat2 a b)
  (cond ((empty? a)   b)
        ((empty? b)   a)
        (else (balance (wt-first b) a (_wt-delmin b)))))

; ?? no cmp
(define (_wt-concat3 v l r)
  (balance v l r)) #|
  (cond ((empty? l)   (node/add cmp r v))
        ((empty? r)   (node/add cmp l v))
        (else (match-let ([#(rv rl rr rw) r]
                          [#(lv ll lr lw) l])
                (cond ((< (* wt-tree-ratio lw) rw) (t-join rv (_wt-concat3 v l rl) rr))
                      ((< (* wt-tree-ratio rw) lw) (t-join lv ll (_wt-concat3 v lr r)))
                      (else (N v l r))))))) |#

;; (a -> a -> integer) -> wt -> a -> wt
; TODO: with less comparator
(define (wt-split< cmp node x)
  (let loop ([node node])
    (match node
      ['()         '()]
      [#(v l r _)  (if3 (cmp x v)
                        (loop l)
                        l
                        (_wt-concat3 v l (loop r)))]
      [v           (if3 (cmp x v)
                        '()
                        '()
                        v)])))

;; (a -> a -> integer) -> wt -> a -> wt
; TODO: with less comparator
(define (wt-split> cmp node x)
  (let loop ([node node])
    (match node
      ['()         '()]
      [#(v l r _)  (if3 (cmp x v)
                        (_wt-concat3 v (loop l) r)
                        r
                        (loop r))]
      [v           (if3 (cmp x v)
                        v
                        '()
                        '())]
      )))

(define (wt-union cmp tree1 tree2)
  (iter->wt
   (iter-merge cmp
               (wt->iter tree1)
               (wt->iter tree2))))

(define (wt-intersection cmp tree1 tree2)
  (iter->wt
   (iter-intersection cmp
                      (wt->iter tree1)
                      (wt->iter tree2))))


; node -> (a -> boolean) -> (node node)
; TODO: (wt-search node less) -- less-comparator or less-closure as for binary-search 

; node -> (a -> integer) -> (node node)
; TODO: (wt-search-3 node cmp) -- cmp-comparator or cmp-closure ?

; TODO?: wt-ref-range
; TODO?: wt-del-range
; TODO?: wt-ins-range

; get item at given position
; wt -> integer -> a
(define (wt-ref node i)
  (unless (and (<= 0 i) (< i (wt-length node)))
    (error (format "ref: index ~a is out of range [0;~a]" i (sub1 (wt-length node)))))
  (let loop ([i i][node node])
    (match node 
      [#(v l r _)  (let ([lw (wt-length l)])
                     (if3 (integer-compare i lw)
                          (loop i l)
                          v
                          (loop (- i lw 1) r)))]
      [v      (=! i 0) ; N1=identity
              v])))

; insert item at given position
;; wt -> integer -> a -> wt
(define (wt-ins node i x)
  (unless (and (<= 0 i (wt-length node)))
    (error (format "ins: index ~a is out of range [0;~a]" i (wt-length node))))
  (let loop ([i i][node node])
    (match node 
      ['()        x]
      [#(v l r _) (let ([lw (wt-length l)])
                    (if3 (integer-compare i lw)
                         (balance v (loop i l) r)
                         (N x l (N v '() r)) ; TODO?: do balance
                         (balance v l (loop (- i lw 1) r))))]
      [v          (=! i 0)
                  (N x '() v)])))

(define (wt-ins+ node i n getter)
  (error "TODO")
  )

; insert items between given positions
;; wt -> integer -> integer -> wt
(define (wt-del node i1 i2)
  (error "TODO") ; concat slices
  )

(define (wt-slice node [start 0] [end (wt-length node)])
  (error "TODO") 
  )


; (car it) = value

; wt -> number -> wti
(define (wt-ref-it node i)
  (unless (and (<= 0 i) (< i (wt-length node)))
    (error (format "ref-it: index ~a is out of range [0;~a]" i (sub1 (wt-length node)))))
  (let loop ([i i][node node] [ii '()])
    (match node
      ['()         (error)]
      [#(v l r _)  (let ([lw (wt-length l)])
                     (if3 (integer-compare i lw)
                          (loop i l (cons node ii))
                          (cons* v node ii)
                          (loop (- i lw 1) r (cons node ii))))]
      [v      (=! i 0) ; N1=identity
              (cons v ii)])))

;; wti -> number
(define (wti-n ii)  
  (parameterize ([match-equality-test eq?])
    (let loop ([ii ii] [sum 0])
      (match ii
        [(_)                   sum]
        [(t #(_ t _ _) _ ...)  (loop (cdr ii) sum)]
        [(t #(t l _ _) _ ...)  (loop (cdr ii) (+ sum (wt-length l)))]
        [(t #(_ l t _) _ ...)  (loop (cdr ii) (+ sum 1 (wt-length l)))]))))

;; wt -> wti
(define (wt-first-it node [ii '()])
  (match node
    ['()           (error "wt-first-it: empty set")]
    [#(v '() _ _)  (cons* v node ii)]
    [#(_   l _ _)  (wt-first-it l (cons node ii))]
    [v             (cons v ii)]))

;; wt -> wti
(define (wt-last-it node [ii '()])
  (match node
    ['()           (error "rb-last-it: empty set")]
    [#(v _ '() _)  (cons* v node ii)]
    [#(_ _   r _)  (wt-last-it r (cons node ii))]
    [v             (cons v ii)]))

;; wti -> wti -> boolean
(define (wti=? i1 . iis)
  ;  (eq? (car i1) (car i2)))
  (every (lambda(ii) (eq? (car ii) (car i1))) iis))

;; wti -> a
(define (wti-value ii)
  (car ii))

;; wti -> wti | #f
(define (wti-next ii) ; TODO: [n 1]
  (parameterize ([match-equality-test eq?])
    (match ii
      ; finish
      [(_)                     #f] 
      ; we were in left branch
      [(t #(v t _ _) _ ...)    (cons v (cdr ii))]
      ; we were in right branch, now go up
      [(t #(_ _ t _) _ ...)    (wti-next (cdr ii))]
      ; we were in value, and there is no way right, now go up
      [(t #(t _ '() _) _ ...)  (wti-next (cdr ii))]
      ; we were in value, now go right branch
      ; then choose left branch until the bottom (as in wt-first-it)
      [(t #(t _ r _) _ ...)    (wt-first-it r (cdr ii))])))

;; wti -> wti | #f
(define (wti-prev ii) ; TODO: [n 1]
  (parameterize ([match-equality-test eq?])
    (match ii
      ; finish
      [(_)                     #f] 
      ; we were in right branch
      [(t #(v _ t _) _ ...)    (cons v (cdr ii))]
      ; we were in left branch, now go up
      [(t #(_ t _ _) _ ...)    (wti-prev (cdr ii))]
      ; we were in value, and there is no way left, now go up
      [(t #(t '() _ _) _ ...)  (wti-prev (cdr ii))]
      ; we were in value, now go left branch
      ; then choose right branch until the bottom (as in wt-last-it)
      [(t #(t l _ _) _ ...)    (wt-last-it l (cdr ii))])))

; get maximum (rightmost) value with edge=#f
(define (wt-edge- node edge?)
  (let loop ([node node])
    (match node
      ['()         #f]
      [#(v l r _)  (if (edge? v)    
                       (loop l) 
                       (or (loop r) ; try to find smtg smaller
                           v))]     ; or take v, it is ok
      [v           (if (edge? v) #f v)])))

; get minimum (leftmost) value with edge=#t
(define (wt-edge+ node edge?)
  (let loop ([node node])
    (match node
      ['()         #f]
      [#(v l r _)  (if (edge? v)    ; v is ok
                       (or (loop l) ; try to find smtg smaller
                           v)
                       (loop r))]
      [v           (if (edge? v) v #f)])))

; get minimum (leftmost) cursor with edge=#t
(define (wt-edgei+ node edge?)
  (let loop ([node node] [ii '()])
    (match node
      ['()         #f]
      [#(v l r _)  (if (edge? v)
                       (or (loop l (cons node ii))
                           (cons* v node ii))
                       (loop r (cons node ii)))]
      [v           (if (edge? v)
                       (cons v ii)
                       #f)])))

; TODO: find iterator for the start point, find a node (or value?) for the stop point
;; wt -> iter<a>
(define (wt->iter node)
  (make-iter (wt-first-it node)
             not ;(lambda(i) (eq? i #f))
             wti-next
             wti-value))

; iter from startedge (inclusive) till stopedge (exclusive)
(define (wt->iter+ node startedge? [stopedge? #f])
  (define stopv (and stopedge?
                     (wt-edge+ node stopedge?))) ; can be #f
  (make-iter (wt-edgei+ node startedge?)
;             not;(lambda(i) (eq? i stopv))
             (lambda(i) (or (eq? i #f) 
                            (eq? (wti-value i) stopv)) )
             wti-next
             wti-value))


;; wt -> iter<a>
(define (wt->iter/backward s)
  (make-iter (wt-last-it s)
             not ;(lambda(i) (eq? i #f))
             wti-prev
             wti-value))

;; wt -> iter<a>
(define (wt->iter/slow-test-variant node)
  (define len (wt-length node))
  (make-iter 0
             (lambda(i) (= i len))
             add1
             (lambda(i) (wt-ref node i))))

#|
(define cc '())
(set! cc (wt-replace bytes-compare cc #"YA.RU"))
(set! cc (wt-replace bytes-compare cc #"YO.RU"))
(set! cc (wt-replace bytes-compare cc #"ZO.RU"))
(wt-ref cc 0)
(wt-ref cc 1)
(wt-ref cc 2)
|#
#|
; +TEST
(define (x-compare a b)
  (define (->num x)
    (cond [(bytes? x) (bytes->number x)]
          [(string? x) (string->number x)]
          [(inexact? x) (inexact->exact x)]
          [else x]))
  (integer-compare (->num a) (->num b)))

(equal! (build-list 7 (lambda(i) (wt-ref-it (wt 1 2 3 4 5 6 7) i)))
        (build-list 7 (lambda(i) (wt-edgei+ (wt 1 2 3 4 5 6 7) (curry < i)))))

(equal! #( 1 2 3 4 5 6 7 #f #f #f)
        (build-vector 10 (lambda(i) (wt-edge+ (wt 1 2 3 4 5 6 7) (curry <  i)))))

(equal! #(#f 1 2 3 4 5 6 7 7 7)
        (build-vector 10 (lambda(i) (wt-edge- (wt 1 2 3 4 5 6 7) (curry <  i)))))


;(define bb '())
(define lst '(#"1111" #"2222" #"3333" #"4444" #"5555" #"6666"))
(define bb (wt/sort x-compare #"3333" #"6666" #"1111" #"5555" #"4444" #"2222"))

;(wt-get x-compare bb 6666)

(equal! lst
        (wt->list bb) 
        (wt->list (list->wt lst))
        (wt->list (apply wt lst)))

; wt-first wt-last
(equal! (wt-first bb) (first lst))
(equal! (wt-last bb)  (last lst))

; wt-remove 
(equal! (wt->list (wt-remove x-compare bb #"0000")) (remove (curry equal? #"0000") lst))
(equal! (wt->list (wt-remove x-compare bb #"1111")) (remove (curry equal? #"1111") lst))
(equal! (wt->list (wt-remove x-compare bb #"2222")) (remove (curry equal? #"2222") lst))
(equal! (wt->list (wt-remove x-compare bb #"3333")) (remove (curry equal? #"3333") lst))
(equal! (wt->list (wt-remove x-compare bb #"4444")) (remove (curry equal? #"4444") lst))
(equal! (wt->list (wt-remove x-compare bb #"5555")) (remove (curry equal? #"5555") lst))
(equal! (wt->list (wt-remove x-compare bb #"6666")) (remove (curry equal? #"6666") lst))
(equal! (wt->list (wt-remove x-compare bb #"0000")) (remove (curry equal? #"7777") lst))

; wt-fold wt-fold-right
(equal! (wt-fold       cons '() bb)
        (fold cons '() lst))
(equal! (wt-fold-right cons '() bb)
        (fold-right cons '() lst))

; wt-iter
(iter->list (wt->iter bb))

; wt-iter
(equal! (iter->list (wt->iter bb))
        (iter->list (wt->iter/slow-test-variant bb))
        (reverse (iter->list (wt->iter/backward bb)))
        (wt->list bb))

; wt-ref
(equal! (build-list (wt-length bb) (lambda(i) (wti-n (wt-ref-it bb i))))
        '(0 1 2 3 4 5))

(equal! (build-list (wt-length bb) (lambda(i) (wti-value (wt-ref-it bb i))))
        (build-list (wt-length bb) (lambda(i) (wt-ref bb i)))
        '(#"1111" #"2222" #"3333" #"4444" #"5555" #"6666"))

; wt-union wt-difference wt-intersection
(equal! '(#"1111" #"2222" 3333 #"4444" #"5555" 6666)
        (wt->list (wt-union x-compare
                            (wt/sort x-compare         #"1111" #"5555" #"4444" #"2222")
                            (wt/sort x-compare 3333 6666 1111 5555))))
#;(equal! '(#"2222" #"4444")
          (wt->list (wt-difference x-compare
                                   (wt/sort x-compare                 #"1111" #"5555" #"4444" #"2222")
                                   (wt/sort x-compare #"3333" #"6666" #"1111" #"5555"                ))))
; TODO: join function to procude result if element exists in both
#;(equal! '(1111 5555)
          (wt->list (wt-intersection x-compare
                                     (wt/sort x-compare         #"1111" #"5555" #"4444" #"2222")
                                     (wt/sort x-compare 3333 6666 1111 5555))))
(equal! '(#"1111" #"2222" #"3333" #"4444" #"5555" #"6666")
        (wt->list (wt-union x-compare
                            (wt/sort x-compare                 #"1111"         #"4444" #"2222")
                            (wt/sort x-compare #"3333" #"6666"         #"5555"                ))))
#;(equal! '(#"1111" #"2222" #"4444")
          (wt->list (wt-difference x-compare
                                   (wt/sort x-compare                #"1111"         #"4444" #"2222")
                                   (wt/sort x-compare #"3333" #"6666"         #"5555"                ))))
#;(equal! '()
          (wt->list (wt-intersection x-compare
                                     (wt/sort x-compare                 #"1111"         #"4444" #"2222")
                                     (wt/sort x-compare #"3333" #"6666"         #"5555"                ))))

;(true! (wti=? (rb-refi s 0) (rb-geti= cmp 1111 s)))
;(true! (wti=? (rb-refi s 1) (rb-geti= cmp 2222 s)))
;(true! (wti=? (rb-refi s 2) (rb-geti= cmp 3333 s)))
;(true! (wti=? (rb-refi s 3) (rb-geti= cmp 4444 s)))
;(true! (wti=? (rb-refi s 4) (rb-geti= cmp 5555 s)))
;(true! (wti=? (rb-refi s 5) (rb-geti= cmp 6666 s)))


(false!                                                     (wti-prev (wt-ref-it bb 0)) )
(true!  (wti=?                             (wt-ref-it bb 0) (wti-prev (wt-ref-it bb 1)) ))
(true!  (wti=? (wti-next (wt-ref-it bb 0)) (wt-ref-it bb 1) (wti-prev (wt-ref-it bb 2)) ))
(true!  (wti=? (wti-next (wt-ref-it bb 1)) (wt-ref-it bb 2) (wti-prev (wt-ref-it bb 3)) ))
(true!  (wti=? (wti-next (wt-ref-it bb 2)) (wt-ref-it bb 3) (wti-prev (wt-ref-it bb 4)) ))
(true!  (wti=? (wti-next (wt-ref-it bb 3)) (wt-ref-it bb 4) (wti-prev (wt-ref-it bb 5)) ))
(true!  (wti=? (wti-next (wt-ref-it bb 4)) (wt-ref-it bb 5) ))
(false!        (wti-next (wt-ref-it bb 5)) )


; wt->iter+
(equal! '(3 4 5)
        (iter->list (wt->iter+ (wt 1 2 3 4 5 6 7) (curryr > 2) (curryr > 5))))
(equal! '(2 3 4)
        (iter->list (wt->iter+ (wt 1 2 3 4 5 6 7) (curryr >= 2) (curryr >= 5))))
(equal! '(3 4 5 6 7)
        (iter->list (wt->iter+ (wt 1 2 3 4 5 6 7) (curryr > 2))))
; wt-edge+
(equal! #( 1 2 3 4 5 6 7 #f #f #f)
        (build-vector 10 (lambda(i) (wt-edge+ (wt 1 2 3 4 5 6 7) (curryr >  i)))))
(equal! #(1 1 2 3 4 5 6 7 #f #f)
        (build-vector 10 (lambda(i) (wt-edge+ (wt 1 2 3 4 5 6 7) (curryr >= i)))))
; wt-edge-
(equal! #(#f 1 2 3 4 5 6 7 7 7)
        (build-vector 10 (lambda(i) (wt-edge- (wt 1 2 3 4 5 6 7) (curryr >  i)))))
(equal! #(#f #f 1 2 3 4 5 6 7 7)
        (build-vector 10 (lambda(i) (wt-edge- (wt 1 2 3 4 5 6 7) (curryr >=  i)))))


; wt-ins
(equal! (build-list 7 (lambda(i) (wt->list (wt-ins bb i #"aaaa"))))
        '((#"aaaa" #"1111" #"2222" #"3333" #"4444" #"5555" #"6666")
          (#"1111" #"aaaa" #"2222" #"3333" #"4444" #"5555" #"6666")
          (#"1111" #"2222" #"aaaa" #"3333" #"4444" #"5555" #"6666")
          (#"1111" #"2222" #"3333" #"aaaa" #"4444" #"5555" #"6666")
          (#"1111" #"2222" #"3333" #"4444" #"aaaa" #"5555" #"6666")
          (#"1111" #"2222" #"3333" #"4444" #"5555" #"aaaa" #"6666")
          (#"1111" #"2222" #"3333" #"4444" #"5555" #"6666" #"aaaa")))

#;(wt->list
   (node/union x-compare
               (list->wt x-compare '())
               (list->wt x-compare '())))

(equal! '(#"3333" #"6666" #"1111" #"5555" #"4444" #"2222" #"3434")
        (wt->list (wt-concat (wt #"3333" #"6666" #"1111" #"5555" #"4444" #"2222")
                             (wt #"3434"))))

(equal! '(#"3333" #"6666" #"1111" #"aaaa" #"5555" #"4444" #"2222")
        (wt->list (_wt-concat3 #"aaaa"
                               (wt #"3333" #"6666" #"1111")
                               (wt #"5555" #"4444" #"2222"))))


(equal! '(#"4444" #"5555" #"6666")
        (wt->list (wt-split> x-compare bb #"3333"))
        (wt->list (wt-split> x-compare bb #"3344")))
(equal! '(#"1111" #"2222")
        (wt->list (wt-split< x-compare bb #"3333")))
(equal! '(#"1111" #"2222" #"3333")
        (wt->list (wt-split< x-compare bb #"3344")))

(equal! '(1 'aa + 3.0 #f #:qq 0+1i)
        (wt->list (list->wt '(1 'aa + 3.0 #f #:qq +i))))


;(exit)

(define aa '())

(define rnd100k (build-vector 10000 (lambda(i)
                                       (number->bytes (random-integer #e9e9))
                                       ) ))
#;(define rnd100k (build-vector 100000 (lambda(i)
                                         (number->bytes i)
                                         ) ))
;(o 'aaa)
;(collect-garbage)
(o 'bbb)
(time   (vector-for-each (lambda(i v)
                           (set! aa (wt-replace bytes-compare aa v))
                           ;(wt-tree/add! aa k 0)
                           ;                           (set! s (rb-insert x-compare k s))
                           ) rnd100k)  )
(=! (wt-length aa) (vector-length rnd100k))

(time (set! rnd100k (vector-sort bytes<? rnd100k)) )
(equal! (wt->vector aa)
        rnd100k)


(define i 0)
(wt-for-each (lambda(v)
               (true! (bytes=? (vector-ref rnd100k i) v))
               (inc! i)
               ) aa)

(wt-mheight aa)
(wt-height aa)

;(wt-tree/fold (lambda(k v init) (cons k init)) '() aa)

;|#